package work.xiaohong.arithmetic.SortArithmetic;

/**
 * @author xiaohong
 * @version 1.0
 * @date 2021/10/27 0027 9:39
 * @description 插入排序
 */
public class Insertion {

    /**
     * 排序原理
     * 1.把所有的元素分为两组，已经排序的和未排序的;
     * 2.找到未排序的组中的第一个元素，向已经排序的组中进行插入;
     * 3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，
     * 那么就把待插入元素放到这个位置，其他的元素向后移动一位;
     *
     * 时间复杂度分析
     * 元素比较的次数
     * （N-1）+(N-2)+...+2+1 = ((N-1)+1)*N/2 = N^2/2-N/2
     * 元素的交换次数
     * （N-1）+(N-2)+...+2+1 = ((N-1)+1)*N/2 = N^2/2-N/2
     * 总执行次数
     * (N^2/2-N/2)+(N^2/2-N/2) = N^2-N
     * 所以时间复杂度为O(N^2)
     *
     * 稳定的排序算法
     *
     */

    public static void insertSort(Comparable[] arr){
        for (int i = 1; i < arr.length; i++) {  // 从下标为1开始，第一个元素不需要比较
            for (int j = i; j > 0; j--) {
                if (SortUtils.greater(arr[j-1],arr[j])){
                    // 前面的元素比当前元素大，交换位置
                    SortUtils.swap(arr,j,j-1);
                }else {
                    // 找到了比当前元素小的，退出循环
                    break;
                }
            }
        }
    }


}
